package com.whitedust.top10;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

class LRUCache {
    private static class Node{
        int key;
        int value;
        Node(int k,int v){
            key=k;
            value=v;
        }
        Node pre;
        Node next;
    }
    private int capacity;
    private Node dummy = new Node(0,0);
    private HashMap<Integer,Node> hashMap = new HashMap<>();
    public LRUCache(int capacity){
        this.capacity=capacity;
        dummy.pre = dummy;
        dummy.next = dummy;
    }
    public int get(int key){
        Node node = getNode(key);
        if(node==null)return -1;
        return node.value;
    }
    public void put(int key,int val){
        Node node = getNode(key);
        if(node!=null){
            node.value = val;
            return;
        }
        if(hashMap.size()==capacity){
            Node removeNode = dummy.pre;
            remove(removeNode);
            hashMap.remove(removeNode.key);
        }
        Node newNode = new Node(key,val);
        hashMap.put(key,newNode);
        putFront(newNode);
    }
    private void remove(Node node){
        node.pre.next =node.next;
        node.next.pre = node.pre;
    }
    private void putFront(Node node){
        node.next =dummy.next;
        node.pre = dummy;
        dummy.next.pre = node;
        dummy.next = node;
    }
    private Node getNode(int key){
        if(!hashMap.containsKey(key))return null;
        Node node = hashMap.get(key);
        remove(node);
        putFront(node);
        return node;
    }
}